One of the challenges in image segmentation algorithms is incorporating shape priors. Graph-based segmentation algorithms have recently gained in popularity. Without using shape priors, the graph-based segmentation methods such as minimum cuts (see Y. Boykov and M. P. Jolly, “Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images,” In Proc. of ICCV 2001, pp. 105-112, 2001), Normalized Cuts (see J. Shi and J. Malik, “Normalized Cuts and Images Segmentation,” IEEE PAMI, 22(8):888-905, August 2000), isoperimetric partitioning (see L. Grady and E. L. Schwartz, “Isoperimetric Graph Partitioning for Image Segmenation,” IEEE Trans. on Pat. Anal. And Mach. Int., 28(3):469-475, March 2006) and random walker (see L. Grady, “Multilabel Random Walker Image Segmentation Using Prior Models,” In Proc. of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 1, pp. 763-770, San Diego, June 2005) provide steady-state, globally optimal solutions. For example, the Normalized Cuts algorithm is a graph partitioning algorithm that has previously been used successfully for image segmentation. It is originally applied to pixels by considering each pixel in the image as a node in the graph. To improve these graph-based segmentation methods, attempts have been made to incorporate shape information into these segmentation algorithms. These attempts, however, have destroyed the global optimality of the solutions and required an initialization.
Several attempts have been made to incorporate shape information into graph-based segmentation algorithms, but so far all of them have yielded algorithms that do not provide global optimality. One of these approaches was introduced by Freedman and Zhang (see D. Freedman and T. Zhang, “Interactive Graph Cut Based Segmentation with Shape Priors,” In Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 1, pp. 755-762, 2005), where they assume that the shape has a fixed template that may be translated, rotated and scaled. They first fit the shape to the image and construct a distance map, which is later added as an additional term to the energy functional. The solution is found using graph cuts with binary labeling (see Y. Boykov, O. Veksler and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE PAMI, 23(11):1222-1239, November 2001) among several image scales, and selecting the one with minimum normalized energy score. Tolliver et al. (see D. Tolliver, G. L. Miller and R. T. Collins, “Corrected Laplacians: Closer Cuts and Segmentation with Shape Priors,” In Proc. of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 2, pp. 92-98, 2005) proposed an iterative algorithm for shape based segmentation. They first parameterize the shapes using Principal Component Analysis on the space formed by training shapes. At each subsequent iteration, they find a shape model for the existing segmentation and guide the segmentation using this shape model. Another approach taken by Kumar et al. (see M. P. Kumar, P. H. torr and A. Zisserman, “OBJ CUT,” In Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 1, pp. 18-25, 2005) was to add a shape prior term in a Markov Random Field segmentation framework. This shape prior term was updated after each segmentation in a Expectation Maximization framework to produce a solution with local energy minimum. In a similar framework, Slabaugh and Unal (see G. Slabaugh and G. Unal, “Graph Cut Segmentation Using an Elliptical Shape Prior,” In 2005 IEEE International Conference on Image Processing, 2005) proposed using elliptical shape priors in the context of graph cuts segmentation. In their work, the cut is constrained to lie on an elliptical band which is also updated iteratively according to the result of previous segmentation. All of these methods rely on guiding the image cut with an estimate of the shape.
The drawbacks of these shape-based segmentation algorithms require an initialization and, thus, do not provide globally optimal solution. It is difficult to predict or describe their behavior. Therefore, an improved shape-based segmentation algorithm is desired that provides globally optimal solution that does not require initialization, allows thorough analysis and predict its behavior.